USACO 题解
USACO 2021 Dec 月赛已经结束了。作者本届USACO难度整体难度偏高, 每个组别的难度都有显著的提升。尤其Bronze组别和Silver组别, 题目逐渐需要一定的算法知识, 而不是可以轻松解决的了。
Bronze组别的题目数据范围都有一定的提升, 算法的效率也变成了考核的一部分了。
本次月赛的Silver T3是在每周社团时间讲过的FFT, 快速傅立叶变换算法, 成功押题!
本次金组题目难度适中, 其中Gold T3看起来非常计算几何, 但是考虑到其中的关系的话其实本质上是一个森林! 如果没有考虑到可能这道题就会很不好做了。
本次铂金组题目难度适中, 但是由于作者没有成功完成解答, 故不对题目进行分析。
本次题目难度评级依然使用[入门, 普及, 提高, 省选]作为大难度标签, 将使用[I-IV] 作为小难度标签。评级仅代表作者个人观点。
Bronze T1 [入门 \(\rm{IV}\)]
枚举左端点 L, 若令满足题目要求的对应的连续右端点为 [R1,R2], 则 R1, R2 分别单调递增。因此考虑双指针分别维护 L, R1, R2 即可。
Bronze T2 [入门 \(\rm{VI}\)]
首先令 \(p_i\) 和 \(t_i\) 做差。后考虑每一次连续的区间加操作本质上是对于差分数组前后两个位置分别 +x, -x。后模拟即可。
Bronze T3 [普及 \(\rm{IV}\)]
动态规划, dp[i][j][k][l] 表示走到了 i 行 j 列转弯 k 次, 其中目前的朝向是 l 即可。但是考虑到 k 很小, 可以做出更简单的求解。
Silver T1 [提高 \(\rm{III}\)]
考虑到连续两个对方的牛之间, 我们只需要使用两头牛即可占领这区间所有的草堆。因此每个区间放的奶牛数量必然为 1 或者 2。预处理出放一头牛的收益 c1, 和放两头牛的收益 c2, 求解即可。由于 c1>c2-c1, 可以使用堆, 贪心的取最大的若干个。
Silver T2 [普及 \(\rm{IV}\)]
首先并查集处理出联通块。有两种情况, 放一条边和放两条边。放一条边的只能从 1 号在的联通块建立到 n 号在的联通块。简单二分即可。第二种情况是 1->x->n 的这种情况, 考虑枚举联通块x, 中的节点, 然后同样简单二分即可。
Silver T3 [提高 \(\rm{I}\)/省选 \(\rm{I}\)]
开桶, 直接按照题目要求FFT乘法卷积即可。可以注意到卷积的英文是Convolution, 而题目的名字是Convoluted Intervals.
Gold T1 [提高 \(\rm{III}\)]
观察到一定是两个两个相邻的成对。直接dp即可。注意需要维护一下奇偶性。
Gold T2 [提高 \(\rm{III}\)]
可以考虑从大到小枚举x+0.5, 只有x-1, x, x+1 可能会随之变化。用平衡树维护答案即可。
Gold T3 [提高 \(\rm{I-V}\)]
可以发现不同的Polygon之间只有包含关系, 不能有相交关系。这个形式可以被化作为一颗树, 其中给定的序列即是目前树的括号序列。建树后判断即可。